package com.ryujung.array.leetCode_88;
/*
 * @lc app=leetcode.cn id=88 lang=java
 *
 * [88] 合并两个有序数组
 */

import java.util.Arrays;

// @lc code=start
class Solution {

    /**
     * 将两个有序数组（正序）合并到nums1中，要求合并后nums1仍然为有序数组（正序）;
     * 
     * 主要思路（归并排序的一部分算法）：
     * 
     * 将两个数组从倒序遍历，对比大小，获取最大的数放在nums1中，
     * 然后将较大数所在的数组，角标向前一格，
     * 
     * 直到nums2中的所有元素都已被遍历，或
     * 
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1;
        int index2 = n - 1;
        int len = m + n;
        while (len > 0 && index2 >= 0) {
            nums1[--len] = (index1 >= 0 && nums1[index1] >= nums2[index2]) ? nums1[index1--] : nums2[index2--];
        }
    }

    public static void main(String[] args) {
        // int[] arr1 = { 1, 2, 3, 0, 0, 0 };
        // int[] arr2 = { 2, 5, 6 };
        int[] arr1 = { 0 };
        int[] arr2 = { 1 };
        System.out.println(Arrays.toString(arr1));
        merge(arr1, arr1.length - arr2.length, arr2, arr2.length);
        System.out.println(Arrays.toString(arr1));
    }
}
// @lc code=end
